package 中等.动态规划.子序列;

/**
 * 一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。
 * 比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。
 * 给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从 0 开始编号）。
 * 一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成
 * 的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列（加粗元素），但是 [2,4,2] 不是。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-alternating-subsequence-sum
 */
public class 最大子序列交替和_1911 {

    public static void main(String[] args) {

    }

    /**
     * 动态规划
     * 1，子问题：
     * dp[i] 表示[0,i]的最大子序列交替和是多少
     * 2，状态转移方程
     * dp[i] 的最大和只与 [0,i-1] 中最大偶数子序列或最大奇数子序列有关
     * 当前数字+前面最大奇数子序列=最大偶数子序列
     * 当前数字+前面最大偶数子序列=最大奇数子序列
     */
    public long maxAlternatingSum(int[] nums) {
        long oddSum = 0, evenSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            long tOdd = oddSum;

            oddSum = Math.max(oddSum, evenSum - nums[i]);

            evenSum = Math.max(evenSum, tOdd + nums[i]);

        }

        return Math.max(oddSum, evenSum);
    }

}
